

#include <stdlib.h>
#include <stdio.h>
#include "mymonitor.h"

#define BACKOFF_POINT 75

/* Queue to hold threads that are blocked */
mythread_queue_t *blockedQueue = NULL;
/* Number of blocked threads, used to easily broadcast all threads to wake up */
int numBlockedThreads = 0;

/* Queue to hold threads that have backed off */
mythread_queue_t *backedOffQueue = NULL;
/* Number of threads that have been blocked due to backing off */
int numBackedOffThreads = 0;

/* Flag that indicates whether the queue has been priorly initialized */
int initFlag = 0;

/**
 * Initializes a monitor_t struct for use
 *
 *@param m  monitor_t variable to be initialized
 */
int monitor_init(monitor_t *m){
	/* Malloc the monitor pointer and then set its members to their default starting values */
	m = (monitor_t *) malloc(sizeof(monitor_t));
	if (m == NULL) {
		printf("Unable to initialize monitor; no more memory available\n");
		return 0;
	}
	m->locked = 0;
	m->signalReady = 0;
	m->broadcastReady = 0;
	
	/* Initialize blockedQueue and backedOffQueue the first time you create a monitor */
	if(initFlag == 0){
		blockedQueue = (mythread_queue_t *) malloc(sizeof(mythread_queue_t));
		if (blockedQueue == NULL) {
			printf("Unable to create blocked queue; no more memory available\n");
			return 1;
		}
		
		backedOffQueue = (mythread_queue_t *) malloc(sizeof(mythread_queue_t));
		if (backedOffQueue == NULL) {
			printf("Unable to create blocked queue; no more memory available\n");
			return 1;
		}
		
		initFlag = 1;
	}
	
	return 1;
}

/**
 * Enters the monitor using spinlock and backoff after 75 cycles
 *
 *@param m  monitor_t variable to be entered
 */
int monitor_enter(monitor_t *m){
	/* Keeps track of the number of attempts so that we can backoff at 75 */
	int attempts = 0;
	
	/* Compare_and_swap to enter the monitor, essentially waiting for m->locked to be 0 */
	while(compare_and_swap(&(m->locked), 1, 0) != 0){
		attempts++;
		/* If you have reached the backoff point, then enter the kernel and spin one more time */
		if(attempts == BACKOFF_POINT){
			mythread_enter_kernel();
			
			/* If the extra spin fails, then it is time to block this thread on the backedOffQueue until a thread exits the monitor, then backedoff threads will be awakened to contend again */
			if(compare_and_swap(&(m->locked), 1, 0) != 0){
				/* Add one more to number of threads that have backedOff and been blocked */
				numBackedOffThreads++;
	
				/* printf("Backing off in enter!\n"); */
				
				mythread_block(backedOffQueue, 1);
				
				attempts = 0;
			} else {
				mythread_leave_kernel();
				/* We successfully entered the monitor */
				break;
			}
		}
	}
	
	/* printf("Thread: Enter successful\n"); */
	return 1;
}

/**
 * Exits the monitor and handles logic behind signal and braodcast that cannot be done during the middle of monitor execution (because we would context switch away within the monitor
 *
 *@param m  monitor_t variable to be exited
 */
int monitor_exit(monitor_t *m){
	mythread_enter_kernel();
	
	/* printf("Thread: Exit successful\n"); */
	/* Set the lock of the monitor back to 0, because it is no longer held by this thread */
	m->locked = 0;
	
	/* Check to see if the thread that was just in the monitor called monitor_signal, if so then signal the thread at the head of the blockedQueue to wake up, first you must obtain the monitor via spinlock */
	if(m->signalReady == 1){
		/* Reset signal flag to default */
		m->signalReady = 0;
		
		/* Make sure the signal call comes when there are blocked threads, otherwise simply skip this work */
		if(numBlockedThreads > 0){
			int attempts = 0;
			mythread_leave_kernel();
			/* Spin outside of the kernel to gain the monitor so that we can legally awake a blocked thread, knowing it will wake up within the monitor */
			while(compare_and_swap(&(m->locked), 1, 0) != 0){
				attempts++;
				if(attempts == BACKOFF_POINT){
								
					if(compare_and_swap(&(m->locked), 1, 0) != 0){
						mythread_enter_kernel();
						
						numBackedOffThreads++;
                        /* printf("Backing off in signal!\n"); */
						
						mythread_block(backedOffQueue, 1);
													
						attempts = 0;
					} else {
						/* We successfully entered the monitor */
						break;
					}
				}
			}
		
			/* Reenter the kernel after return from block call */
			mythread_enter_kernel();
		
			/* Indicate that one thread is being unblocked, then unblock it */
			numBlockedThreads--;
			mythread_unblock(blockedQueue,0);
		
			/* Reenter the kernel, so that exit may continue */
			mythread_enter_kernel();
		}
	}
	
	/* Check to see if the thread that was just in the monitor called monitor_broadcast, if so then signal all threads in the blockedQueue to wake up, first you must obtain the monitor via spinlock, each time you wake one up */
	if(m->broadcastReady == 1){
		m->broadcastReady = 0;
		
		/* Make sure the broadcast call comes when there are blocked threads, otherwise simply skip this work */
		if(numBlockedThreads > 0){
		    /* Save the number of currently blocked threads, so that we only unblock the threads that are blocked at the time of this call */
			int numBlocked = numBlockedThreads;
			
			/* Loop through the blockedQueue awakening as many threads as numBlocked */
			int i = 0;
			for(;i < numBlocked;i++){
				int attempts = 0;
				mythread_leave_kernel();
				/* Spin outside of the kernel to gain the monitor so that we can legally awake a blocked thread, knowing it will wake up within the monitor */
				while(compare_and_swap(&(m->locked), 1, 0) != 0){
					attempts++;
					if(attempts == BACKOFF_POINT){
								
						if(compare_and_swap(&(m->locked), 1, 0) != 0){
							mythread_enter_kernel();
						
							numBackedOffThreads++;
							/* printf("Backing off in broadcast!\n"); */
						
							mythread_block(backedOffQueue, 1);
							
							attempts = 0;
						} else {
							/* We successfully entered the monitor */
							break;
						}
					}
				}
		
				/* Reenter the kernel after return from block call */
				mythread_enter_kernel();
				
				/* Indicate that one thread is being unblocked, then unblock it */
				numBlockedThreads--;
				mythread_unblock(blockedQueue,0);
				
				/* Reenter the kernel, so that exit may continue */
				mythread_enter_kernel();
			}
		}
	}
	
	/* If there are backed off threads, then unblock them so that they can start contesting the monitor again */
	if(numBackedOffThreads > 0){
		/* Save the number of currently backed off threads, so that we only wake those up */
		int numBackedOff = numBackedOffThreads;
		int i = 0;
		/* Loop through unblocking the number above of backedOffThreads */
		for(;i < numBackedOff;i++){
			numBackedOffThreads--;
			mythread_unblock(backedOffQueue,0);
			mythread_enter_kernel();
		}
	}
	
	/* Leave the kernel entirely once exit has completed */
	mythread_leave_kernel();
	
	return 1;
}

/**
 * Destroys the monitor struct, by setting all variables to invalid values
 *
 *@param m  monitor_t variable to be destroyed
 */
int monitor_destroy(monitor_t *m){
	mythread_enter_kernel();

	m->locked = 100; /* Indicates that monitor struct is not valid */
	m->signalReady = -1; /* Indicates that monitor struct is not valid */
	m->broadcastReady = -1; /* Indicates that monitor struct is not valid */
	
	mythread_leave_kernel();
	
	return 1;
}

/**
 * Signals a thread blocked for the monitor to wake up, the actual wake up occurs on monitor_exit
 *
 *@param m  monitor_t variable to be signalled
 */
int monitor_signal(monitor_t *m){  
   mythread_enter_kernel();
   
   /* Indicate to the exit function that this monitor should signal a blocked thread to wake up on exit */
   m->signalReady = 1;
   
   mythread_leave_kernel();
   
   return 1;  
}

/**
 * Signals all threads blocked for the monitor to wake up, the actual wake up occurs on monitor_exit
 *
 *@param m  monitor_t variable to be broadcast to
 */
int monitor_broadcast(monitor_t *m){
    mythread_enter_kernel();
	
	/* Indicate to the exit function that this monitor should signal all blocked threads to wake up on exit */
	m->broadcastReady = 1;
	
	mythread_leave_kernel();
	
	return;
 }	

/**
 * Blocks a thread waiting for the monitor to be signalled that it should wake up
 *
 *@param m  monitor_t variable that this thread will be waiting on, and that it is currently operating within
 */
int monitor_wait(monitor_t *m){
	mythread_enter_kernel();
	
	/* Increase the number of threads that are blocked */
	numBlockedThreads++;
	
	/* Prepare the queues for blocking */
	mythread_block_phase1(blockedQueue, 1);
	
	mythread_enter_kernel();
	
	/* Exiting the monitor */
	m->locked = 0;
	
	/* If there are backed off threads, then unblock them so that they can start contesting the monitor again */
	if(numBackedOffThreads > 0){
		/* Save the number of currently backed off threads, so that we only wake those up */
		int numBackedOff = numBackedOffThreads;
		int i = 0;
		/* Loop through unblocking the number above of backedOffThreads */
		for(;i < numBackedOff;i++){
			numBackedOffThreads--;
			mythread_unblock(backedOffQueue,0);
			mythread_enter_kernel();
		}
	}
	
	/* Actually block current thread, activating the next in line */
	mythread_block_phase2();
	
	return 1;
}
